In order to promote reliability of various digital systems, it has become necessary to apply error correction codes in recent years. Various kinds of error correction codes have been adopted corresponding to various systems.
In particular, Reed Solomon code (hereinafter referred to as RS code) is an important code which has low redundancy and is widely used in the fields of CD (Compact Disk), DAT (Digital Audio Tape) and satellite communication.
There are various methods proposed for decoding RS code. For correction of a few symbols, for instance, two or three symbols, it is possible to obtain error locations and error values through an algebraic function using RS code and it is easy to devise a decoder for this purpose. However, in a system requiring high reliability, it is necessary to increase the error correction capability. In this case, the Peterson algorithm, the Berlekamp-Massey algorithm or the Euclid's algorithm is used. In these algorithms, decoding is performed by setting up error locator polynomials and error evaluator polynomials and obtaining error locations and error values according to the Chien searcher. Circuits for enabling this type of decoding are extremely large and require large calculation times.
Next, the RS code will be briefly described.
The RS code comprises Galois field GF elements. If a code length is n, the minimum distance (Hamming distance) is d, and having k information bearing symbols in an RS code on Galois field GF(2.sup.n) comprising 2.sup.n elements, the RS code satisfies the following equations (1) and (2): EQU n.ltoreq.2.sup.n -1 (1) EQU n=k+(d-1) (2)
The error correction capability t of this RS code can be expressed by the following equation (3): EQU t=(d-1)/2 (3)
A generator polynomial G(X) has degrees equivalent to code check symbols (n-k) (=d-1=2t) and is divisible X.sup.n-1. If the primitive element of GF(2.sup.n) is .alpha., the generator polynomial G(X) of the RS code can be expressed by the following equation (4): EQU G(X)=(X-.alpha.).multidot.(X-.alpha..sup.2) . . . (X-.alpha..sup.2t)(4)
Further, G(X) can optionally be replaced by the following equation (5). EQU G(X)=(X-1).multidot.(X-.alpha.) . . . (X-.alpha..sup.2t-1) (5)
Next, the encoding will be described.
A coding polynomial C(X), once encoded must be divisible by a generator polynomial G (X). If an information symbol of size k to be encode is I and this information is expressed by a polynomial, the information-bearing symbol polynomial I is expressed by the following equation (6): EQU I(X)=Cn-1.multidot.X.sup.n-1 +Cn-2.multidot.X.sup.n-2 +Cn-k.multidot.X.sup.n-k ( 6)
A residue polynomial, P(X), obtained by dividing the information-bearing symbol polynomial G(X) by the generator polynomial P(X) is expressed by the following equation (7). ##EQU1## and a coding polynomial C(X) is provided by the following equation (8): EQU C(X)=I(X)+P(X) (8)
It is apparent that the coding polynomial, C(X), of the equation (8) is divisible by G(X).
Next, the encoding will be described.
FIG. 1 is a circuit diagram showing a conventional decoder for decoding error correction code. The decoder shown in FIG. 1 is that disclosed in the Japanese Patent Official Gazette (TOKU-KO-HEI) 4-7847.
The decoder shown in FIG. 1 is based on the systolic algorithm. If no erasure is taken into considertion, the decoding is carried out following procedures (1) through (5):
(1) Syndrome calculation is carried out. PA1 (2) If all syndromes are 0, it is judged that there is no error. PA1 (3) Using the Peterson algorithm or Euclid's algorithm, an error locator polynomial .sigma.(X) and an error value polynomial .omega. (X) are obtained. PA1 (4) According to the Chien searcher, a root of .sigma. (X), i.e., an error location is obtained. PA1 (5) A root of .omega. (X), an error value is obtained.
The coding polynomial C(X) of equation (8) is subjected to the effects of noise in a transmission line and changes to a received polynomial Y(X). This received polynomial Y(X) is the sum of the coding polynomial C(X) and the error evaluator polynomial .sigma. (X).
First, in step (1), syndromes S1, S2, . . . S2t are calculated from the received polynomial Y(X). In a BCH code having roots of .alpha., .alpha..sup.2, . . . , .alpha..sup.2t, syndromes are defined by the equation (9): EQU Si=Y(.alpha..sup.i), (i=1,2, . . . , 2t) (9)
As C(.alpha.i)=0, (i=1,2, . . . 2t), a syndrome will be: EQU Si=E(.alpha..sup.i), (i=1, 2, . . . , 2t) (10)
and if there is no error, all the syndromes will become 0.
Errors e1, e2, . . . , eL are generated at locations j1, j2, . . . jL, where L.ltoreq.t. The following equation (11) is also established; EQU E(X)=e1.multidot.X.sup.j1 +e2.multidot.X.sup.j2 + . . . +eL.multidot.X.sup.jL ( 11)
equation (12) is obtained from the-equation (10). ##EQU2##
Therefore, error locations j1, j2 . . . , jL and error values e1, e2 . . . , eL can be obtained from the S1, S . . . S2t.
However, it is difficult to obtain the error values directly from syndromes. We first obtain an L degree polynomial on the Galois field GF(2.sup.n) shown in the equation (13): EQU .sigma.(Z)=(1-.alpha..sup.jl .multidot.Z).multidot.(1-.alpha..sup.j2 .multidot.Z) . . . (1-.alpha..sup.jL .multidot.Z) (13)
Equation (13) is called an error locator polynomial with roots that correspond to error locations.
If syndrome S(Z) is assumed to be as shown by equation (14), and attention is paid to equation (15), equation (16) is obtained: ##EQU3##
When .sigma.(Z) is applied to both sides of the equation (16), the following equation (17) is obtained: EQU .sigma.(Z).multidot.S(Z)=.omega.(Z).multidot.mod Z.sup.2t ( 17)
Equation (17) can be replaced by equation (18), in using an appropriate polynomial A(Z). EQU A(Z).multidot.Z.sup.2t +.sigma.(Z).multidot.S(Z) (18)
.omega. (Z) of equation (18) is called an error evaluator polynomial and is defined by equation (19). ##EQU4##
Here, relations of [deg .sigma. (Z).ltoreq.t] and [deg .omega. (Z).ltoreq.t-1] (deg denotes degree) are established. Further, as [.omega.(.alpha..sup.-i1).noteq.0] (i=1, . . . , L) and both .omega. (Z) and .sigma. (Z) disjoint one another, it is possible to obtain .omega. (Z) and .sigma. (Z) in the process of the Euclid's algorithm for obtaining the greatest common divisor (GCD) polynomial of Z.sup.2t and S(Z).
Next, Euclid's algorithm that is adopted in Procedure (3) will be described.
Now, when two polynomials r-1 (Z) and r0 (Z) are applied and deg r0.ltoreq.deg r-1, the following divisions (20) through (23) are repeated. EQU r-1(Z)=q1(Z).multidot.r0 (Z)+r1 (Z), deg r1.ltoreq.deg r0 (20) EQU R0 (Z)=q2 (Z).multidot.r1 (Z)+r2 (Z), deg r2.ltoreq.deg r1 (21) EQU rj-2(Z)=qj(Z).multidot.rj-1(Z)+r1 (Z), deg rj.ltoreq.deg rj-1(23) EQU rj-1(Z)=qj+1(Z).multidot.rj(Z) (24)
And, the last divided non-zero rj(Z) becomes the greatest common divisor (GCD) of r-1(Z) and r0 (Z).
Here, the following theorem is used.
When two polynomials r-1(Z) and r0 (Z) are applied, deg r0 .ltoreq.deg r-1 and GCD=h(Z) which satisfy, there exist U(Z) and V(Z) equation (24) and both deg U and deg V are smaller than deg r-1. EQU U(Z).multidot.r-1(Z)+V(Z).multidot.r0(Z)=h(Z) (24)
Assuming r-1(Z)=Z.sup.2t and r0(Z)=S(Z), polynomials ri(Z), Ai(Z) and Bi(Z) satisfy equation (25) are sequentially calculated using the above theorem. EQU A(Z).multidot.r-1(Z)+Bi(Z).multidot.r0(Z)=ri(Z) (25)
And if Bi(Z) becomes less than degree t and residue ri(Z) becomes less than deg (t-1), Bi(Z) and ri(Z) become possible substitutes of .epsilon. (Z) and .omega. (Z), respectively. Therefore, assuming that A-1 (Z)=1, A0(Z)=0, B-1(Z)=0 and B0 (Z)=1, ri (Z) , Ai (Z) and Bi (Z) are calculated as shown below. EQU ri(Z)=ri-2(Z)-qi(Z).multidot.ri-1(Z) (26) EQU Ai(Z)=Ai-2(Z)-qi(Z).multidot.Ai-1(Z) (27) EQU Bi(Z)=Bi-2(Z)-qi(Z).multidot.Bi-1(Z) (28)
And when the degree of ri(Z) becomes less than (t-1) through the above arithmetic operations, the following equations (29) and (30) are obtained. EQU .sigma.1(Z)=Bi(Z) (29) EQU .omega.1(Z)=ri(Z) (30)
An error value ei is obtained according to the following equation (31) by using the roots of .sigma. (X) and .omega. (X) obtained through Euclid's algorithm. EQU ei=-.omega.(.alpha..sup.-ji)/.sigma.'(.alpha..sup.-ji), (i=1, . . . , L)(31)
where, .sigma.' (Z) is a derivative of .sigma. (Z), which is a differential of .sigma. (Z). This .sigma.'(Z) is expressed by the following equations (32) and (32) which are composed of only odd numbered terms taken out of .sigma. (Z). EQU .sigma.'(Z)=.sigma.1+.sigma.3.multidot.Z.sup.2 +.sigma.5.multidot.Z.sup.4 + . . . +.sigma.L.multidot.Z.sup.L-1 (L:odd number) (32) EQU .sigma.'(Z)=.sigma.1+.sigma.3.multidot.Z.sup.2 +.sigma.5.multidot.Z.sup.4 + . . . +.sigma.L.multidot.Z.sup.L-2 (L:even number) (33)
Encoding and decoding of RS code are thus completed.
Further, the decoder, as shown in FIG. 1, has not only the erasure correcting function but also the erasure correcting function using an erasure locator flag signal. An erasure locator flag is used to indicate that a symbol seems erroneous. A flag output circuit 201 outputs this erasure locator flag in synchronism with a received code-word that is input through the input terminal r.in. An erasure locator coefficient .alpha.i indicating an erasure location is generated by erasure locator generator 202.
On the other hand, a received code-word that is input through the input terminal r.in is supplied to a syndrome cell circuit 203 to generate a syndrome S(X). The erasure locator coefficient .alpha..sup.i and syndrome S(X) are supplied to an erasure locator coefficient latch 205 and a modified syndrome cell circuit 206 through an interface (hereinafter referred to as I/F) 204. The modified syndrome cell circuit 206 prepares a modified syndrome S.epsilon. (X) with erasure locator information removed from information on the syndrome S(X). FIG. 2 is a block diagram showing a specified arrangement of the modified syndrome cell circuit 206.
The modified syndrome cell circuit 206 is arranged by connecting 2t pieces of the cell, as shown in FIG. 2. The syndrome S(X) is supplied to a latch 221 as an input Yin, as shown in FIG. 2. When the latch 221 loads the syndrome S(X), the erasure locator coefficient .alpha..sup.i is input to a latch 222. A control circuit 224 controls latches 225 and 226, adder 227 and a multiplier 228 based on a command from latch 223 and obtains the modified syndrome S(X) by performing a calculation of the following equation (34). EQU S.epsilon.(X)=(X-.alpha..sup.i).multidot.S(X)mod X.sup.2t ( 34)
The result of the calculation is supplied to latch 230 through a multiplier (MUX) 229 and then output therefrom. Further, 2t steps are needed for the calculation of the above equation (34). After the calculation has been completed, the modified syndrome coefficient is held in the register of each cell and the modified syndrome S.epsilon. (X) is output, when the decoder is put in the 2t step output mode.
The modified syndrome S.epsilon. (X) obtained from the modified syndrome cell circuit 206 is supplied to both a GCD (Greatest Common Divisor) cell circuit 208 and an erasure locator coefficient latch 209 through an I/F 207. Further, the outputs from the erasure locator coefficient latch 209 and the GCD cell 208 are supplied to both a multiplier cell circuit 211 and an error-erasure value polynomial latch 212 through an I/F 210. The GCD cell circuit 208 obtains a data of series of coefficients of both an error locator polynomial .sigma. e(X) and an error-erasure value polynomial n(X) from the modified syndrome data series. Further, the multiplier cell circuit 211 obtains coefficient data of an error-erasure value polynomial n(X) from both an error locator polynomial .sigma. e(X) and an erasure locator data series. In addition, the I/F circuit 213 obtains a differential .sigma.' (X) of an error erasure locator polynomial .sigma. (X) and outputs it to an evaluation cell circuit 214 together with the error-erasure value polynomial n(X).
The evaluation cell circuit 214 obtains an error value by the calculation according to the following equation (35) at a location i where an error locator polynomial .sigma.(.alpha..sup.i) becomes 0. EQU n(.alpha..sup.i)/.sigma.'(.alpha..sup.i) (35)
An error value obtained by the evaluation cell circuit 214 is supplied to an adder 216 through a gate circuit 215. This gate circuit 215 determines if an error is generated at the location i when the error locator polynomial .sigma.(.alpha..sup.i) is 0, and supplies the error value to an adder 216. The adder 216, being supplied with a received code-word from a buffer memory 217, corrects an error by an addition of the Galois fields of the data at the received code-word i with an error value at the location i and outputs to an output terminal 218. Where, COMin, as shown in FIG. 1, represents a command input of each circuit.
The decoder, as shown in FIG. 1, is capable of pipeline processing and is excellent in high speed processing. However, it was defective in that it's circuit was too large and uneconomical for processing in a large scale integration.
The longest calculation time is required for the process to obtain the error locator polynomial .sigma. (Z) and the error evaluator polynomial .omega. (Z) from syndromes. The circuit size corresponding to this process is very large. A proposal for reducing the circuit scale of this portion was disclosed in the Japanese Patent Disclosure (TOKU-KAI-SHO) 63-157528. FIGS. 3 and 4 are block diagrams showing this proposal, respectively. FIG. 3 shows processing elements for generating a GCD and FIG. 4 shows the entire circuit arrangement using the processing elements shown in FIG. 3.
In this proposal, a systolic algorithm is adopted. This systolic algorithm obtains .sigma. (X) and .omega. (X) in the same process as for obtaining a GCD using the Euclid's algorithm, and the degree is reduced by alternately multiplying the maximum degree coefficients of two polynomials. Further, in the actual circuit, in order to obtain .sigma. (X) and .omega. (X), it is necessary to use the circuit twice, as shown in FIG. 4, or to provide two circuit systems.
Thus, in a conventional Euclid's algorithm operation circuit, one basic processing circuit is composed of two multipliers, an adder, a three-input two-output multiplexer and seven registers. The circuit scale is extremely large, as shown in FIG. 3. If one symbol is comprised of 8 bits as in, for instance, RS code on a Galois field GF(2.sup.8), when the number of gates is obtained in a unit of NAND gate, it is necessary to arrange about 1.2K gates.
Actually, (2t+2) pieces of this basic circuit are used and therefore, if 2t=10, 14.4K gates must be arranged. Further, to assure a high speed decoding, it is necessary to provide two circuits, as shown in FIG. 4, as the circuit cannot be used twice. In this case, if LDC (Long Distance Code) is adopted and it is assumed that [2t=16], then 21600 gates will be required, resulting in an enormous circuit scale.
As described above, a conventional decoder has a problem in that its circuit scale is too large be suitable for large scale integration.